package com.kingbook.common.utils;

import java.io.Serializable;
import java.security.SecureRandom;

public class BloomFilter64bit implements Serializable {

    private static final long serialVersionUID = 2317000663009608403L;

    /**
     * The number of weights used to create hash functions.
     */
    final public static int NUMBER_OF_WEIGHTS = 2083; // CHANGED FROM 16
    /**
     * The number of bits in this filter.
     */
    final public long m;
    /**
     * The number of hash functions used by this filter.
     */
    final public int d;
    /**
     * The underlying bit vector.
     */
    final private long[] bits;
    /**
     * The random integers used to generate the hash functions.
     */
    final private long[][] weight;

    /**
     * The number of elements currently in the filter. It may be
     * smaller than the actual number of additions of distinct character
     * sequences because of false positives.
     */
    private int size;

    /**
     * The natural logarithm of 2, used in the computation of the number of bits.
     */
    private final static double NATURAL_LOG_OF_2 = Math.log(2);

    private final static boolean DEBUG = false;

    public BloomFilter64bit() {
        this(10000000, 22);
    }

    public BloomFilter64bit(int n) {
        this(n, 22);
    }

        /**
         * Creates a new Bloom filter with given number of hash functions and expected number of elements.
         *
         * @param n the expected number of elements.
         * @param d the number of hash functions; if the filter add not more than <code>n</code> elements,
         *          false positives will happen with probability 2<sup>-<var>d</var></sup>.
         */
    public BloomFilter64bit(final int n, final int d) {
        this.d = d;
        int len = (int) Math.ceil(((long) n * (long) d / NATURAL_LOG_OF_2) / 64L);
        if (len / 64 > Integer.MAX_VALUE)
            throw new IllegalArgumentException("This filter would require " + len * 64L + " bits");
        bits = new long[len];
        m = bits.length * 64;

        if (DEBUG) System.err.println("Number of bits: " + m);

        // seeded for reproduceable behavior in repeated runs; BUT: 
        // SecureRandom's default implementation (as of 1.5) 
        // seems to mix in its own seeding.
        final SecureRandom random = new SecureRandom(new byte[]{19, 96});
        weight = new long[d][];
        for (int i = 0; i < d; i++) {
            weight[i] = new long[NUMBER_OF_WEIGHTS];
            for (int j = 0; j < NUMBER_OF_WEIGHTS; j++)
                weight[i][j] = random.nextLong();
        }
    }

    /**
     * The number of character sequences in the filter.
     *
     * @return the number of character sequences in the filter (but see {@link #contains(CharSequence)}).
     */

    public int size() {
        return size;
    }

    /**
     * Hashes the given sequence with the given hash function.
     *
     * @param s a character sequence.
     * @param l the length of <code>s</code>.
     * @param k a hash function index (smaller than {@link #d}).
     * @return the position in the filter corresponding to <code>s</code> for the hash function <code>k</code>.
     */

    private long hash(final CharSequence s, final int l, final int k) {
        final long[] w = weight[k];
        long h = 0;
        int i = l;
        while (i-- != 0) h ^= s.charAt(i) * w[i % NUMBER_OF_WEIGHTS];
        return (h & 0x7FFFFFFFFFFFFFFFL) % m;
    }

    /**
     * Checks whether the given character sequence is in this filter.
     * <p>
     * <P>Note that this method may return true on a character sequence that is has
     * not been added to the filter. This will happen with probability 2<sub>-<var>d</var></sub>,
     * where <var>d</var> is the number of hash functions specified at creation time, if
     * the number of the elements in the filter is less than <var>n</var>, the number
     * of expected elements specified at creation time.
     *
     * @param s a character sequence.
     * @return true if the sequence is in the filter (or if a sequence with the
     * same hash sequence is in the filter).
     */

    public boolean contains(final CharSequence s) {
        int i = d, l = s.length();
        while (i-- != 0) if (!getBit(hash(s, l, i))) return false;
        return true;
    }

    /**
     * Adds a character sequence to the filter.
     *
     * @param s a character sequence.
     * @return true if the character sequence was not in the filter (but see {@link #contains(CharSequence)}).
     */

    public boolean add(final CharSequence s) {

        boolean result = false;
        int i = d, l = s.length();
        long h;
        while (i-- != 0) {
            h = hash(s, l, i);
            if (!getBit(h)) result = true;
            setBit(h);
        }
        if (result) size++;

        return result;
    }

    protected final static long ADDRESS_BITS_PER_UNIT = 6; // 64=2^6
    protected final static long BIT_INDEX_MASK = 63; // = BITS_PER_UNIT - 1;

    /**
     * Returns from the local bitvector the value of the bit with
     * the specified index. The value is <tt>true</tt> if the bit
     * with the index <tt>bitIndex</tt> is currently set; otherwise,
     * returns <tt>false</tt>.
     * <p>
     * (adapted from cern.colt.bitvector.QuickBitVector)
     *
     * @param bitIndex the bit index.
     * @return the value of the bit with the specified index.
     */
    protected boolean getBit(long bitIndex) {
        return ((bits[(int) (bitIndex >> ADDRESS_BITS_PER_UNIT)] & (1L << (bitIndex & BIT_INDEX_MASK))) != 0);
    }

    /**
     * Changes the bit with index <tt>bitIndex</tt> in local bitvector.
     * <p>
     * (adapted from cern.colt.bitvector.QuickBitVector)
     *
     * @param bitIndex the index of the bit to be set.
     */
    protected void setBit(long bitIndex) {
        bits[(int) (bitIndex >> ADDRESS_BITS_PER_UNIT)] |= 1L << (bitIndex & BIT_INDEX_MASK);
    }

    /* (non-Javadoc)
     * @see org.archive.util.BloomFilter#getSizeBytes()
     */
    public long getSizeBytes() {
        return bits.length * 8;
    }
}
